class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& nums) {
        int j = 1, n = nums.size();
        for (int i = 0; i < nums.size();) {
            while (i < n && nums[i] % 2 == 0)
                i += 2;
            while (j < n && nums[j] % 2 == 1)
                j += 2;

            if (i < n && j < n)
                swap(nums[i], nums[j]);
            else
                break;
        }
        return nums;
    }
};